package sivan.letcode;

import org.junit.Test;

import java.util.*;

//https://leetcode-cn.com/problems/two-sum/
public class LetCode2 {

    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int count = 1;
        int index = 1;
        while (index < nums.length) {
            if (nums[index] != nums[index - 1]) {
                nums[count] = nums[index];
                count++;
            }
            index++;
        }

        return count;
    }

    public static int removeElement(int[] nums, int val) {
        if (nums.length == 0) {
            return 1;
        }

        int count = 0;
        int right = 0;
        int left = nums.length - 1;
        while (left >= right) {
            if (nums[right] != val) {
                count++;
                right++;
                continue;
            }
            if (nums[left] != val) {
                int temp = nums[right];
                nums[right] = nums[left];
                nums[left] = temp;
                right++;
                count++;
            }
            left--;
        }
        return count;
    }

    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    public int searchInsert(int[] nums, int target) {
        if (target <= nums[0]) {
            return 0;
        }
        for (int i = 0; i < nums.length - 1; i++) {
            if (target >= nums[i] && target <= nums[i + 1]) {
                return i + 1;
            }
        }
        return nums.length;
    }

    public static int maxSubArray(int[] nums) {
        int pre = 0;
        int max = nums[0];
        for (int num : nums) {
            pre = Math.max(pre + num, num);
            max = Math.max(pre, max);
        }
        return max;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 两两交换
     *
     * @param head
     * @return
     */
    public ListNode swapPairs(ListNode head) {
        if (head == null) {
            return head;
        }

        ListNode a = head.next;
        if (a == null) {
            return head;
        }

        ListNode b = a.next;
        head.next = b;
        a.next = head;
        swap(head);
        return a;
    }

    public void swap(ListNode head) {
        ListNode a = head.next;
        if (a == null) {
            return;
        }

        ListNode b = a.next;
        if (b == null) {
            return;
        }
        ListNode c = b.next;
        head.next = b;
        b.next = a;
        a.next = c;
        swap(a);
    }

    /**
     * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
     * k 是一个正整数，它的值小于或等于链表的长度。
     * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
     *
     * @param head
     * @param k
     * @return
     */
    ListNode newHead = null;
    List<ListNode> list = new ArrayList<>();

    public ListNode reverseKGroup(ListNode head, int k) {
        if (k == 1) {
            return head;
        }

        List<ListNode> list = new ArrayList<>(k);
        list.add(head);
        ListNode n = head;
        for (int i = 0; i < k - 1; i++) {
            ListNode next = n.next;
            if (next != null) {
                n = next;
                list.add(next);
            } else {
                return head;
            }
        }

        ListNode lastNext = list.get(k - 1).next;
        ListNode pre = null;
        for (int i = k - 1; i >= 0; i--) {
            if (pre == null) {
                newHead = list.get(i);
                pre = newHead;
            } else {
                pre.next = list.get(i);
                pre = list.get(i);
            }
        }

        pre.next = lastNext;
        insertList(pre, k);
        return newHead;
    }

    public void insertList(ListNode pre, int k) {

        ListNode n = pre;
        for (int i = 0; i < k; i++) {
            ListNode next = n.next;
            if (next != null) {
                n = next;
                list.add(next);
            } else {
                return;
            }
        }

        ListNode lastNext = list.get(k - 1).next;
        for (int j = k - 1; j >= 0; j--) {
            pre.next = list.get(j);
            pre = list.get(j);
        }

        pre.next = lastNext;
        list.clear();
        insertList(pre, k);
    }

    public int strStr(String haystack, String needle) {
        int length = haystack.length();
        int length2 = needle.length();
        if (length == 0 && length2 == 0) {
            return 0;
        }
        if (length2 == 0) {
            return 0;
        }
        if (length < length2) {
            return -1;
        }

        if (length == length2) {
            if (haystack.equals(needle)) {
                return 0;
            }
            return -1;
        }

        char[] a = haystack.toCharArray();
        char[] b = needle.toCharArray();
        for (int i = 0; i < length; i++) {
            if (a[i] != b[0]) {
                continue;
            }

            if (i + length2 > length) {
                return -1;
            }

            if (a[i + length2 - 1] == b[length2 - 1]) {
                if (haystack.substring(i, i + length2).equals(needle)) {
                    return i;
                }
            }
        }
        return -1;
    }

    public int divide(int dividend, int divisor) {
        boolean flag = false;
        if ((dividend > 0 && divisor > 0)
                || (dividend < 0 && divisor < 0)) {
            flag = true;
        }

        if (divisor == 1) return dividend;
        if (divisor == -1) {
            if (dividend > Integer.MIN_VALUE) return -dividend;
            return Integer.MAX_VALUE;
        }
        int a = Math.abs(dividend);
        int b = Math.abs(divisor);
        if (b > a) {
            return 0;
        }

        int result = 1;
        int sum = b;
        while (sum < a) {
            sum <<= 1;
            result <<= 1;
            while (sum > a) {
                sum -= b;
                result--;
            }
        }

        return flag ? result : -result;
    }

    static class Node {
        int value;
        Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        Node d = new Node(4, null);
        Node c = new Node(3, d);
        Node b = new Node(2, c);
        Node a = new Node(1, b);
        Node f = re(a);
        System.out.println();
    }

    public static Node re(Node head) {
        Node a = head;
        Node node = null;
        while (a != null) {
            if (node == null) {
                node = new Node(a.value, null);
            } else {
                node = new Node(a.value, node);
            }
            a = a.next;
        }
        return node;
    }

    @Test
    public void longestValidParentheses() {
        String s = "()(()";
        char[] arr = s.toCharArray();
        int l = arr.length;
        if (l <= 1) {
            return;
        }
        Deque<Integer> deque = new ArrayDeque<>();
        deque.push(-1);
        int max = 0;
        for (int i = 0; i < l; i++) {
            char c = arr[i];
            if (c == '(') {
                deque.push(i);
            } else {
                deque.pop();
                if (deque.isEmpty()) {
                    deque.push(i);
                } else {
                    max = Math.max(max, i - deque.peek());
                }
            }
        }
    }


    public int[] searchRange(int[] nums, int target) {
        if (nums.length < 1) {
            return new int[]{-1, -1};
        }
        int left = 0;
        int right = nums.length - 1;
        int begin = -1;
        int end = -1;
        while (left <= right) {
            if (nums[left] == target) {
                begin = left;
                end = left;
                break;
            }
            left++;
        }
        while (left < right) {
            if (nums[right] == target) {
                end = right;
                break;
            }
            right--;
        }

        return new int[]{begin, end};
    }

    /**
     * 判断是否有重复字符串
     *
     * @param astr
     * @return
     */
    public boolean isUnique(String astr) {
        Set<Character> set = new HashSet<>();
        BitSet set1 = new BitSet();
        char[] arr = astr.toCharArray();
        for (char c : arr) {
            if (set1.get(c)) {
                return false;
            } else {
                set1.set(c);
            }
        }
        return true;
    }

    /**
     * 判定是否互为字符重排
     *
     * @param s1
     * @param s2
     * @return
     */
    public boolean CheckPermutation(String s1, String s2) {
        char[] arr1 = s1.toCharArray();
        char[] arr2 = s2.toCharArray();
        int l1 = arr1.length;
        int l2 = arr2.length;
        if (l1 != l2) {
            return false;
        }

        for (char c : arr1) {
            for (int j = 0; j < l2; j++) {
                char c2 = arr2[j];
                if (c == c2) {
                    arr2[j] = '\0';
                    break;
                }
                if (j == l2 - 1) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 取代空白字符
     *
     * @param S
     * @param length
     * @return
     */
    public String replaceSpaces(String S, int length) {
//        char[] arr = S.toCharArray();
//        StringBuilder builder = new StringBuilder();
//        for (int i = 0; i < length; i++) {
//            if (arr[i] == ' ') {
//                builder.append("%20");
//            } else {
//                builder.append(arr[i]);
//            }
//        }
//        return builder.toString();
        char[] arr = S.toCharArray();
        int index = arr.length - 1;
        for (int i = length - 1; i >= 0; i--) {
            if (arr[i] == ' ') {
                arr[index--] = '0';
                arr[index--] = '2';
                arr[index--] = '%';
            } else {
                arr[index--] = arr[i];
            }
        }
        return new String(arr, index + 1, arr.length - index - 1);
    }

    public boolean canPermutePalindrome(String s) {
        char[] arr = s.toCharArray();
        BitSet set = new BitSet();
        for (char c : arr) {
            boolean flag = set.get(c);
            if (flag) {
                set.clear(c);
            } else {
                set.set(c);
            }
        }
        int total = set.cardinality();
        return total == 1 || total == 0;
    }

    public boolean oneEditAway(String first, String second) {
        int f = first.length();
        int s = second.length();

        if (Math.abs(f - s) > 1) return false;
        if (first.equals(second)) return true;

        int count = 0;    // 记录不匹配的次数。
        int i = 0, j = 0; // 用来指向两字符串的指针
        while (i < f && j < s) {
            // 两个字符串从前往后开始遍历，如果当前两字符串字符相同就继续比较下一个。
            if (first.charAt(i++) == second.charAt(j++)) {

                continue;
            }
            count++;
            if (count > 1) return false;

            if (f != s) { // 若不相等，则将短字符串指针前移一位

                if (f > s) j--;
                else i--;
            }
        }
        return true;
    }

    public boolean deal(char[] arr1, char[] arr2) {
        int count = 0;
        int index = 0;
        for (int i = 0; i < arr1.length; i++) {
            if (i < arr2.length + 1) {
                if (index < arr2.length && arr1[i] != arr2[index]) {
                    if (count == 0) {
                        count++;
                        index = i + 1;
                    } else {
                        return false;
                    }
                } else {
                    if (index < arr2.length - 1) {
                        index++;
                    }
                }
            } else {
                if (count == 0) {
                    count++;
                } else {
                    return false;
                }
            }
        }
        return true;
    }


    /**
     * 字符重复出现的次数
     *
     * @param S
     * @return
     */
    public String compressString(String S) {
        char[] arr = S.toCharArray();
        if (arr.length <= 0) {
            return S;
        }
        StringBuilder builder = new StringBuilder();
        int count = 1;
        char temp = arr[0];
        for (int i = 1; i < arr.length; i++) {
            char c = arr[i];
            if (c == temp) {
                count++;
            } else {
                builder.append(temp).append(count);
                temp = c;
                count = 1;

            }
        }
        builder.append(temp).append(count);
        String result = builder.toString();
        return result.length() < arr.length ? result : S;
    }

    public boolean isFlipedString(String s1, String s2) {
        return s1.length() == s2.length() && (s1 + s1).contains(s2);
    }

    public ListNode removeDuplicateNodes(ListNode head) {
        if (head == null) {
            return head;
        }
        int value = head.val;
        ListNode node = head.next;
        while (node != null) {
            if (node.val == value) {
                
            }
        }
        return  null;
    }
}
